LeetCode - 134.Gas Station
题目大意:
有n
个加油站分布在 环形路线上。其中每个加油站的储油量为 gas[i]
。 你有一辆巨大油箱(可以无限加油)的汽车,从 站点i
到下一站i+1
,油耗为 cost[i]
。一开始的时候,汽车油箱是空的。
如果你能一次开完全程的话,请返回一个起始站点。否则返回-1表示无法完成。
解题思路:
首先可以明确的是,如果 总油耗sum{cost[0...n]}
大于 总储量sum{gas[0...n]}
的话,是无法完成任务的。直接返回-1。
接着,思考一下当 总油耗 小等于 总储量时,是否必然存在可行解。
C(i) + C(i+1) + C(i+2) + C(i+3) … + C(i+n) = C
G(i) + G(i+1) + G(i+2) + G(i+3) … + G(i+n) = G
G >= C
如果 平均分布的话, 则 G(i)>=C(i) 。 必然是ok的。
考虑极限情况,C(i) 油耗巨大。贪心策略保证每站必停(油不加白不加),我们从i站点逆时针
选点。基于贪心考虑,逆时针选站点要保证对经过C(i)最大油耗是有利:每一次后退选点对总油耗是正向的。
枚举 (Time Limit Exceeded)
时间复杂度 大致为 O(n^2)。 测试用例数据极为暴力。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| int goRound(int starInx,int *gas,int gasSize,int *cost,int costSize){ int nowGas = 0; int nowIdx = starInx; for(int i=0;i<gasSize;i++){ nowGas += gas[nowIdx]; if(nowGas < cost[nowIdx]) return -1; nowGas -= cost[nowIdx]; nowIdx = (nowIdx+1)%gasSize; } return nowGas >= 0 ? starInx : -1; }
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) { int ans = -1; int totalGas = 0, totalCosts = 0;
for(int i=0;i<costSize;i++){ totalCosts += cost[i]; } for(int i=0;i<gasSize;i++){ totalGas += gas[i]; } if(totalGas < totalCosts) return ans; for(int i=0;i<gasSize;i++){ if((ans = goRound(i,gas,gasSize,cost,costSize)) != -1){ break; } } return ans; }
|
贪心 (Accepted)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) { int totalGas = 0, totalCosts = 0; int maxCostIdx = -1, maxCost = -1; for(int i=0;i<costSize;i++){ totalCosts += cost[i]; if(cost[i] > maxCost){ maxCostIdx = i; maxCost = cost[i]; } } for(int i=0;i<gasSize;i++){ totalGas += gas[i]; } if(totalGas < totalCosts) return -1; int tmp = maxCostIdx; int tmpMaxgas = gas[tmp]; int tmpMaxCost = cost[tmp]; while (tmpMaxgas < tmpMaxCost || gas[tmp] >= cost[tmp]) { tmp--; if(tmp == -1) tmp = gasSize - 1; if(tmp == maxCostIdx) break; tmpMaxgas += gas[tmp]; tmpMaxCost += cost[tmp]; } return (tmp+1)%gasSize; }
|